home *** CD-ROM | disk | FTP | other *** search
/ PC World 2002 September / PCWorld_2002-09_cd.bin / Software / Vyzkuste / httrack / httrack-3.20RC4.exe / {app} / src / htshash.c < prev    next >
C/C++ Source or Header  |  2002-04-30  |  13KB  |  454 lines
  1. /* ------------------------------------------------------------ */
  2. /*
  3. HTTrack Website Copier, Offline Browser for Windows and Unix
  4. Copyright (C) Xavier Roche and other contributors
  5.  
  6. This program is free software; you can redistribute it and/or
  7. modify it under the terms of the GNU General Public License
  8. as published by the Free Software Foundation; either version 2
  9. of the License, or any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this program; if not, write to the Free Software
  18. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19.  
  20.  
  21. Important notes:
  22.  
  23. - We hereby ask people using this source NOT to use it in purpose of grabbing
  24. emails addresses, or collecting any other private information on persons.
  25. This would disgrace our work, and spoil the many hours we spent on it.
  26.  
  27.  
  28. Please visit our Website: http://www.httrack.com
  29. */
  30.  
  31.  
  32. /* ------------------------------------------------------------ */
  33. /* File: httrack.c subroutines:                                 */
  34. /*       hash table system (fast index)                         */
  35. /* Author: Xavier Roche                                         */
  36. /* ------------------------------------------------------------ */
  37.  
  38. #include "htshash.h"
  39.  
  40. /* specific definitions */
  41. #include "htsbase.h"
  42. #include "htsmd5.h"
  43. #include <stdio.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46. /* END specific definitions */
  47.  
  48. // GESTION DES TABLES DE HACHAGE
  49. // MΘthode α 2 clΘs (adr+fil), 2e cle facultative
  50. // hash[no_enregistrement][pos]->hash est un index dans le tableau gΘnΘral liens
  51. // #define HTS_HASH_SIZE 8191  (premier si possible!)
  52. // type: numero enregistrement - 0 est case insensitive (sav) 1 (adr+fil) 2 (former_adr+former_fil)
  53. #if HTS_HASH
  54. // recherche dans la table selon nom1,nom2 et le no d'enregistrement
  55. // retour: position ou -1 si non trouvΘ
  56. int hash_read(hash_struct* hash,char* nom1,char* nom2,int type) {
  57.   unsigned int cle;
  58.   int pos; 
  59.   // calculer la clΘ de recherche, non modulΘe
  60.   if (type)
  61.     cle = hash_cle(nom1,nom2);
  62.   else
  63.     cle = hash_cle(convtolower(nom1),nom2);         // case insensitive
  64.   // la position se calcule en modulant
  65.   pos = (int) (cle%HTS_HASH_SIZE);
  66.   // entrΘe trouvΘe?
  67.   if (hash->hash[type][pos] >= 0) {             // un enregistrement avec une telle clΘ existe..
  68.     // tester table de raccourcis (hash)
  69.     // pos est maintenant la position recherchΘe dans liens
  70.     pos = hash->hash[type][pos];
  71.     while (pos>=0) {              // parcourir la chaine
  72.       switch (type) {
  73.       case 0:         // sav
  74.         if (strfield2(nom1,hash->liens[pos]->sav)) {  // case insensitive
  75. #if DEBUG_HASH==2
  76.           printf("hash: found shortcut at %d\n",pos);
  77. #endif
  78.           return pos;
  79.         }
  80.         break;
  81.       case 1:         // adr+fil
  82.         if ((strcmp(nom1,jump_identification(hash->liens[pos]->adr))==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  83. #if DEBUG_HASH==2
  84.           printf("hash: found shortcut at %d\n",pos);
  85. #endif
  86.           return pos;
  87.         }
  88.         break;
  89.       case 2:         // former_adr+former_fil
  90.         if (hash->liens[pos]->former_adr)
  91.         if ((strcmp(nom1,jump_identification(hash->liens[pos]->former_adr))==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  92. #if DEBUG_HASH==2
  93.           printf("hash: found shortcut at %d\n",pos);
  94. #endif
  95.           return pos;
  96.         }
  97.         break;
  98.       }
  99.       // calculer prochaine position dans la chaine
  100.       {
  101.         int old=pos;
  102.         pos=hash->liens[pos]->hash_next[type];   // sinon prochain dans la chaine
  103.         if (old==pos)
  104.           pos=-1;         // erreur de bouclage (ne devrait pas arriver)
  105.       }
  106.     }
  107.     
  108.     // Ok va falloir chercher alors..
  109.     /*pos=hash->max_lien;    // commencer α max_lien
  110.     switch (type) {
  111.     case 0:         // sav
  112.       while(pos>=0) {
  113.         if (hash->liens[pos]->hash_sav == cle ) {
  114.           if (strcmp(nom1,hash->liens[pos]->sav)==0) {
  115.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  116. #if DEBUG_HASH==2
  117.             printf("hash: found long search at %d\n",pos);
  118. #endif
  119.             return pos;
  120.           }
  121.         }
  122.         pos--;
  123.       }
  124.       break;
  125.     case 1:         // adr+fil
  126.       while(pos>=0) {
  127.         if (hash->liens[pos]->hash_adrfil == cle ) {
  128.           if ((strcmp(nom1,hash->liens[pos]->adr)==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  129.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  130. #if DEBUG_HASH==2
  131.             printf("hash: found long search at %d\n",pos);
  132. #endif
  133.             return pos;
  134.           }
  135.         }
  136.         pos--;
  137.       }
  138.       break;
  139.     case 2:         // former_adr+former_fil
  140.       while(pos>=0) {
  141.         if (hash->liens[pos]->hash_fadrfil == cle ) {
  142.           if (hash->liens[pos]->former_adr)
  143.             if ((strcmp(nom1,hash->liens[pos]->former_adr)==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  144.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  145. #if DEBUG_HASH==2
  146.             printf("hash: found long search at %d\n",pos);
  147. #endif
  148.             return pos;
  149.           }
  150.         }
  151.         pos--;
  152.       }
  153.     }*/
  154. #if DEBUG_HASH==1
  155.     printf("hash: not found after test %s%s\n",nom1,nom2);
  156. #endif
  157.     return -1;    // non trouvΘ
  158.   } else {
  159. #if DEBUG_HASH==2
  160.     printf("hash: not found %s%s\n",nom1,nom2);
  161. #endif
  162.     return -1;    // non trouvΘ : clΘ non entrΘe (mΩme une fois)
  163.   }
  164. }
  165.  
  166. // enregistrement lien lpos dans les 3 tables hash1..3
  167. void hash_write(hash_struct* hash,int lpos) {
  168.   unsigned int cle;
  169.   int pos; 
  170.   int* ptr;
  171.   //
  172.   if (hash->liens[lpos]) {                       // on sait jamais..
  173.     hash->max_lien = max(hash->max_lien,lpos);
  174. #if DEBUG_HASH
  175.     hashnumber=hash->max_lien;
  176. #endif
  177.     // ΘlΘment actuel sur -1 (fin de chaine)
  178.     hash->liens[lpos]->hash_next[0]=hash->liens[lpos]->hash_next[1]=hash->liens[lpos]->hash_next[2]=-1;
  179.     //
  180.     cle = hash_cle(convtolower(hash->liens[lpos]->sav),"");    // CASE INSENSITIVE
  181.     pos = (int) (cle%HTS_HASH_SIZE);
  182.     ptr = hash_calc_chaine(hash,0,pos);         // calculer adresse chaine
  183.     *ptr = lpos;                   // noter dernier enregistrΘ
  184. #if DEBUG_HASH==3
  185.     printf("[%d",pos);
  186. #endif
  187.     //
  188.     cle = hash_cle(jump_identification(hash->liens[lpos]->adr),hash->liens[lpos]->fil);
  189.     pos = (int) (cle%HTS_HASH_SIZE);
  190.     ptr = hash_calc_chaine(hash,1,pos);         // calculer adresse chaine
  191.     *ptr = lpos;                   // noter dernier enregistrΘ
  192. #if DEBUG_HASH==3
  193.     printf(",%d",pos);
  194. #endif
  195.     //
  196.     if (hash->liens[lpos]->former_adr) {         // former_adr existe?
  197.       cle = hash_cle(jump_identification(hash->liens[lpos]->former_adr),hash->liens[lpos]->former_fil);
  198.       pos = (int) (cle%HTS_HASH_SIZE);
  199.       ptr = hash_calc_chaine(hash,2,pos);         // calculer adresse chaine
  200.       *ptr = lpos;                   // noter dernier enregistrΘ
  201. #if DEBUG_HASH==3
  202.       printf(",%d",pos);
  203. #endif
  204.     }
  205. #if DEBUG_HASH==3
  206.     printf("] "); fflush(stdout);
  207. #endif
  208.   }
  209. #if DEBUT_HASH
  210.   else {
  211.     printf("* hash_write=0!!\n");
  212.     exit(1);
  213.   }
  214. #endif
  215.   //
  216. }
  217.  
  218. // calcul clΘ
  219. // il n'y a pas de formule de hashage universelle, celle-ci semble acceptable..
  220. unsigned long int hash_cle(char* nom1,char* nom2) {
  221.   /*
  222.   unsigned int sum=0;
  223.   int i=0;
  224.   while(*nom1) {
  225.     sum += 1;
  226.     sum += (unsigned int) *(nom1);
  227.     sum *= (unsigned int) *(nom1++);
  228.     sum += (unsigned int) i;
  229.     i++;
  230.   }
  231.   while(*nom2) {
  232.     sum += 1;
  233.     sum += (unsigned int) *(nom2);
  234.     sum *= (unsigned int) *(nom2++);
  235.     sum += (unsigned int) i;
  236.     i++;
  237.   }
  238.   */
  239.   return md5sum32(nom1)
  240.         +md5sum32(nom2);
  241. }
  242.  
  243. // calcul de la position finale dans la chaine des elements ayant la mΩme clΘ
  244. int* hash_calc_chaine(hash_struct* hash,int type,int pos) {
  245. #if DEBUG_HASH
  246.   int count=0;
  247. #endif
  248.   if (hash->hash[type][pos] == -1)
  249.     return &(hash->hash[type][pos]);    // premier ΘlΘment dans la chaine
  250.   pos=hash->hash[type][pos];
  251.   while(hash->liens[pos]->hash_next[type] != -1) {
  252.     pos = hash->liens[pos]->hash_next[type];
  253. #if DEBUG_HASH
  254.     count++;
  255. #endif
  256.   }
  257. #if DEBUG_HASH
  258.   count++;
  259.   longest_hash[type]=max(longest_hash[type],count);
  260. #endif
  261.   return &(hash->liens[pos]->hash_next[type]);
  262. }
  263. #endif
  264. // FIN GESTION DES TABLES DE HACHAGE
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277. // inthash -- simple hash table, using a key (char[]) and a value (ulong int)
  278.  
  279. unsigned long int inthash_key(char* value) {
  280.   return md5sum32(value);
  281. }
  282.  
  283. // Check for duplicate entry (==1 : added)
  284. int inthash_write(inthash hashtable,char* name,long int value) {
  285.   int pos = (inthash_key(name) % hashtable->hash_size);
  286.   inthash_chain* h=hashtable->hash[pos];
  287.   while (h) {
  288.     if (strcmp(h->name,name)==0) {
  289.       h->value.intg=value;
  290.       return 0;
  291.     }
  292.     h=h->next;
  293.   }
  294.   // Not found, add it!
  295.   inthash_add(hashtable,name,value);
  296.   return 1;
  297. }
  298.  
  299. // Increment pos value, create one if necessary (=0)
  300. // (==1 : created)
  301. int inthash_inc(inthash hashtable,char* name) {
  302.   long int value=0;
  303.   int r=0;
  304.   if (inthash_read(hashtable,name,&value)) {
  305.     value++;
  306.   }
  307.   else {    /* create new value */
  308.     value=0;
  309.     r=1;
  310.   }
  311.   inthash_write(hashtable,name,value);
  312.   return (r);
  313. }
  314.  
  315.  
  316. // Does not check for duplicate entry
  317. void inthash_add(inthash hashtable,char* name,long int value) {
  318.   int pos = (inthash_key(name) % hashtable->hash_size);
  319.   inthash_chain** h=&hashtable->hash[pos];
  320.  
  321.   while (*h)
  322.     h=&((*h)->next);
  323.   *h=(inthash_chain*)calloc(1,
  324.                               sizeof(inthash_chain)
  325.                               +
  326.                               strlen(name)+2
  327.                             );
  328.   if (*h) {
  329.     (*h)->name=((char*)(*h)) + sizeof(inthash_chain);
  330.     (*h)->next=NULL;
  331.     strcpy((*h)->name,name);
  332.     (*h)->value.intg=value;
  333.   }
  334. }
  335.  
  336. void* inthash_addblk(inthash hashtable,char* name,int blksize) {
  337.   int pos = (inthash_key(name) % hashtable->hash_size);
  338.   inthash_chain** h=&hashtable->hash[pos];
  339.  
  340.   while (*h)
  341.     h=&((*h)->next);
  342.   *h=(inthash_chain*)calloc(1,
  343.                               sizeof(inthash_chain)
  344.                               +
  345.                               strlen(name)+2
  346.                               +
  347.                               blksize
  348.                             );
  349.   if (*h) {
  350.     (*h)->name = ((char*)(*h)) + sizeof(inthash_chain);
  351.     (*h)->next=NULL;
  352.     strcpy((*h)->name,name);
  353.     (*h)->value.intg = (unsigned long) (char*) ((char*)(*h)) + sizeof(inthash_chain) + strlen(name) + 2;
  354.     return (void*)(*h)->value.intg;
  355.   }
  356.   return NULL;
  357. }
  358.  
  359. int inthash_read(inthash hashtable,char* name,long int* value) {
  360.   int pos = (inthash_key(name) % hashtable->hash_size);
  361.   inthash_chain* h=hashtable->hash[pos];
  362.   while (h) {
  363.     if (strcmp(h->name,name)==0) {
  364.       *value=h->value.intg;
  365.       return 1;
  366.     }
  367.     h=h->next;
  368.   }
  369.   return 0;
  370. }
  371.  
  372. void inthash_init(inthash hashtable) {
  373.   unsigned int i;
  374.   for(i=0;i<hashtable->hash_size;i++) {
  375.     hashtable->hash[i]=NULL;
  376.   }
  377. }
  378.  
  379. void inthash_delchain(inthash_chain* hash,t_inthash_freehandler free_handler) {
  380.   if (hash) {
  381.     inthash_delchain(hash->next,free_handler);
  382.     if (free_handler) {     // pos is a malloc() block, delete it!
  383.       if (hash->value.intg) {
  384.         if (free_handler)
  385.           free_handler((void*)hash->value.intg);
  386.         else
  387.           free((void*)hash->value.intg);
  388.       }
  389.       hash->value.intg=0;
  390.     }
  391.     free(hash);
  392.   }
  393. }
  394.  
  395. void inthash_default_free_handler(void* value) {
  396.   if (value)
  397.     free(value);
  398. }
  399.  
  400. // --
  401.  
  402. inthash inthash_new(int size) {
  403.   inthash hashtable=(inthash)calloc(1,sizeof(struct_inthash));
  404.   if (hashtable) {
  405.     hashtable->hash_size=0;
  406.     hashtable->flag_valueismalloc=0;
  407.     if ((hashtable->hash=(inthash_chain**)calloc(size,sizeof(inthash_chain*)))) {
  408.       hashtable->hash_size=size;
  409.       inthash_init(hashtable);
  410.     }
  411.   }
  412.   return hashtable;
  413. }
  414.  
  415. int inthash_created(inthash hashtable) {
  416.   if (hashtable)
  417.     if (hashtable->hash)
  418.       return 1;
  419.   return 0;
  420. }
  421.  
  422. void inthash_value_is_malloc(inthash hashtable,int flag) {
  423.   hashtable->flag_valueismalloc=flag;
  424. }
  425.  
  426. void inthash_value_set_free_handler(inthash hashtable, t_inthash_freehandler free_handler) {
  427.   hashtable->free_handler = free_handler;
  428. }
  429.  
  430. void inthash_delete(inthash* hashtable) {
  431.   if (hashtable) {
  432.     if (*hashtable) {
  433.       if ((*hashtable)->hash) {
  434.         unsigned int i;
  435.         t_inthash_freehandler free_handler=NULL;
  436.         if ( (*hashtable)->flag_valueismalloc ) {
  437.           if ( (*hashtable)->free_handler )
  438.             free_handler=(*hashtable)->free_handler;
  439.           else
  440.             free_handler=inthash_default_free_handler;
  441.         }
  442.         for(i=0;i<(*hashtable)->hash_size;i++) {
  443.           inthash_delchain((*hashtable)->hash[i],(*hashtable)->free_handler);
  444.           (*hashtable)->hash[i]=NULL;
  445.         }
  446.       }
  447.       free(*hashtable);
  448.       *hashtable=NULL;
  449.     }
  450.   }
  451. }
  452.  
  453.  
  454.